package com.yuanfud.common.util;

/**
 * @author yuanfud
 * @date 2018-06-25-14:12
 * @PACKAGE com.yuanfud.common.util
 **/
public class Levenshtein {
    public static void main(String[] args) {
        String str="今天星期二";
        String[] str1={"今天星期五","数据库的哈萨克觉得","昨天星期三","今天星期一","后天星期六"};
        for (int i=0;i<=str1.length;i++){
            if(levenshtein(str,str1[i]))
                System.out.println(str1[i]);
        }
    }

    /**
     * 莱温斯坦算法计算字符串相似度
     * @param targetStr  需要比较的字符
     * @param resourceStr 源字符
     */
    public static boolean levenshtein(String targetStr,String resourceStr){
        //计算两个字符串的长度
        int len1=targetStr.length();
        int len2=resourceStr.length();
        //建立一个数组，比字符串长度大一个空间
        int[][] dif=new int[len1+1][len2+1];
        //赋初值
        for (int a=0;a<=len1;a++){
            dif[a][0]=a;
        }
        for (int a=0;a<=len2;a++){
            dif[0][a]=a;
        }
        //计算两个字符是否一样
        int temp;
        for (int i=1;i<=len1;i++){
            for (int j=1;j<=len2;j++){
                if(targetStr.charAt(i-1)==resourceStr.charAt(j-1))
                    temp=0;
                else
                    temp=1;
                //取三个值中最小的
                dif[i][j]=min(dif[i-1][j-1]+temp,dif[i][j-1]+1,dif[i-1][j]+1);
            }
        }
        float similarity=1-(float)dif[len1][len2]/Math.max(targetStr.length(),resourceStr.length());
//        System.out.println("字符串1：\""+targetStr+"\" 与字符串2：\""+resourceStr+"\" 比较");
        //取数组右下角的值，同样不同位置代表不同字符串的比较
//        System.out.println("差异步骤："+dif[len1][len2]);
//        System.out.println("相似度："+similarity);
        return similarity>0.75f?true:false;
    }

    /**
     * 得到最小值
     * @param is 可变参数的数值
     * @return
     */
    private static int min(int... is){
        int min=Integer.MAX_VALUE;
        for (int i:is){
            if(min>i)
                min=i;
        }
        return min;
    }
}
